﻿#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

// 判断是否能构成三角形
bool canFormTriangle(int a, int b, int c) {
    return a + b > c && a + c > b && b + c > a;
}

// 计算三角形的面积
double calculateArea(int a, int b, int c) {
    double s = (a + b + c) / 2.0;
    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    int m;
    cout << "Please enter the number of sticks as m:";
    cin >> m;
    if (m < 3) {
        cout <<"Maximum perimeter is"<< 0 << endl <<"Maximum area is" << 0 << endl;
        return 0;
    }
    vector<int> sticks(m);
    cout << "Please enter the length of the sticks in order:";
    for (int i =0; i <m; ++i) {
        cin >> sticks[i];
    }
    sort(sticks.begin(), sticks.end());//对木棍进行排序
    int maxPerimeter = 0;//初始化最大周长
    double maxArea = 0;//初始化最大面积
    //使用双指针技术寻找能构成三角形的最长边组合
    for (int i = m - 1; i >= 2; --i) { // 从最长的木棍开始  
        int left = 0, right = i - 1;
        while (left < right) {
            if (canFormTriangle(sticks[left], sticks[right], sticks[i])) {
                int perimeter = sticks[left] + sticks[right] + sticks[i];
                double area = calculateArea(sticks[left], sticks[right], sticks[i]);

                if (perimeter > maxPerimeter) {
                    maxPerimeter = perimeter;
                }
                if (area > maxArea) {
                    maxArea = area;
                }
                ++left; //++left来避免重复检查
                //不需要同时移动left和right，因为我们已经固定了最长边i
                //移动任意一边都可以找到所有可能的组合（但需要注意避免重复和越界
            }
            else if (sticks[left] + sticks[right] <= sticks[i]) {
                ++left; // 如果当前两边之和小于等于最长边，则增大较短边
                //若left加到与right一样依旧小于i边，则退出while循环，选择下一条i边
            }
        }
    }
    cout << "Maximum perimeter is  "<< maxPerimeter << endl;
    cout << "Maximum area is  ";
    printf("%.4lf\n", maxArea);  // 保留10位小数输出面积  

    return 0;
}